﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _4Gewinnt
{

    /// <summary>
    /// Extends the class Board with the ability to redo previous moves 
    /// With the ability to redo previous moves, we only need to store one game board and just must remember the 
    /// moves which were made at the nodes of the MiniMax search tree, to be able to restore the previous state.
    /// </summary>
    public class RedoBoard
    {
        /// <summary>
        /// Stores the actual game tokens
        /// </summary>
        private GameColor[,] grid;
        /// <summary>
        /// The number of rows of the board (readonly)
        /// </summary>
        public int Rows
        {
            get { return _rows; }
        }
        private int _rows = 6;

        /// <summary>
        /// The number of columns of the board (readonly)
        /// </summary>
        public int Cols
        {
            get { return _cols; }
        }
        private int _cols = 7;

        /// <summary>
        /// The number of consecutive token needed to win
        /// </summary>
        public int ttw
        {
            get { return _ttw; }
        }
        private int _ttw;


        /// <summary>
        /// Initializes a new board
        /// </summary>
        /// <param name="ttw">The number of token needed to win (typically 4)</param>
        public RedoBoard(int ttw)
        {
            this._ttw = ttw;
            grid = new GameColor[_rows, _cols];
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    grid[i, j] = GameColor.Empty;
                }
            }
        }

        /// <summary>
        /// Initializes a new board
        /// </summary>
        /// <param name="ttw">The number of token needed to win (typically 4)</param>
        /// <param name="grid">The grid. gird gets copied during initialization</param>
        public RedoBoard(int ttw, GameColor[,] grid)
        {
            this._ttw = ttw;
            this.grid = new GameColor[_rows, _cols];
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    this.grid[i, j] = grid[i, j];
                }
            }
        }

        /// <summary>
        /// Returns an exact copy of this instance (all fields are copied)
        /// </summary>
        /// <returns>An exact copy of this instance (all fields are copied)</returns>
        public RedoBoard Clone()
        {
            return new RedoBoard(this._ttw, this.grid);
        }

        /// <summary>
        /// Finds a legal move in column <paramref name="c"/>. If there is no legal move in 
        /// <paramref name="c"/> (i.e. the column is full), -1 is returned
        /// </summary>
        /// <param name="c">The column to be searched for a legal move</param>
        /// <returns>The row number r such that (r,<paramref name="c"/>) is a legal move. 
        /// If there is no legal move in <paramref name="c"/>, -1 is returned.</returns>
        public int findLegalRowInColumn(int c)
        {
            //search rows from bottom to top for a free space
            for (int i = _rows - 1; i >= 0; i--)
            {
                if (isFieldFree(i, c))
                    return i;
            }

            //if no free space is found, return -1
            return -1;
        }


        /// <summary>
        /// Checks, whether board position (r,c) is free
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <returns>True if no token is on board position (r,c). False if out of bounds</returns>
        public bool isFieldFree(int r, int c)
        {
            //check obvious things
            if (r < 0 || r >= _rows || c < 0 || c >= _cols)
                return false;

            if (grid[r, c] == GameColor.Empty)
                return true;
            else
                return false;
        }



        /// <summary>
        /// Checks whether it is legal to move to column <paramref name="c"/>
        /// </summary>
        /// <param name="c">The column to move to</param>
        /// <returns>True, if it is legal to move to column <paramref name="c"/></returns>
        public bool isLegalColumn(int c)
        {
            if (grid[0, c] == GameColor.Empty)
                return true;
            else
                return false;
        }

        /// <summary>
        /// Move a token to (r,c). An exception is thrown if move was illegal
        /// </summary>
        /// <param name="color">The color of the token to be moved</param>
        /// <param name="c">The column</param>
        public void moveTo(GameColor color, int c)
        {
            int r = findLegalRowInColumn(c);

            //check whether move is legal
            if (r == -1)
                throw new Exception("Illegal move: You cannot move to (" + r.ToString() + "," + c.ToString() + ")");

            //apply move
            grid[r, c] = color;
        }


        /// <summary>
        /// Returns which player is at (r,c)
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <returns>The player at (r,c)</returns>
        public GameColor playerAt(int r, int c)
        {
            return grid[r, c];
        }


        /// <summary>
        /// Returns true if there are no free spaces on the board
        /// </summary>
        /// <returns>True if there are no free spaces on the board</returns>
        public bool isBoardFull()
        {
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    if (grid[i, j] == GameColor.Empty)
                        return false;
                }
            }
            return true;
        }

        /// <summary>
        /// Returns true if no token is on the field yet
        /// </summary>
        /// <returns>True if no token is on the field yet</returns>
        public bool isBoardFree()
        {
            for (int i = 0; i < _rows; i++)
            {
                for (int j = 0; j < _cols; j++)
                {
                    if (grid[i, j] != GameColor.Empty)
                        return false;
                }
            }
            return true;

        }


        /// <summary>
        /// Checks, whether <paramref name="color"/> has won
        /// </summary>
        /// <param name="color">The color</param>
        /// <returns>True if player has won</returns>
        public bool hasWon(GameColor color)
        {
            int[,] winningPosition;
            return hasWon(color, out winningPosition);
        }


        /// <summary>
        /// Checks, whether <paramref name="color"/> has won
        /// </summary>
        /// <param name="color">The color</param>
        /// <param name="winningPosition">The winning position as 4x2 Matrix</param>
        /// <returns>True if player has won</returns>
        public bool hasWon(GameColor color, out int[,] winningPosition)
        {
            //init winning Position
            winningPosition = new int[_ttw, 2];

            //the number of found continous tokens
            int nTokens;

            //search horizontal: -
            for (int r = 0; r < _rows; r++)
            {
                nTokens = 0;
                for (int c = 0; c < _cols; c++)
                {
                    //if token is found
                    if (grid[r, c] == color)
                    {
                        nTokens++;
                        winningPosition[nTokens - 1, 0] = r;
                        winningPosition[nTokens - 1, 1] = c;
                    }
                    else
                        nTokens = 0;
                    //if ttw tokens are found: the player has won, return true
                    if (nTokens == _ttw)
                        return true;
                }
            }

            //search vertical: |
            for (int c = 0; c < _cols; c++)
            {
                nTokens = 0;
                for (int r = 0; r < _rows; r++)
                {
                    //if token is found
                    if (grid[r, c] == color)
                    {
                        nTokens++;
                        winningPosition[nTokens - 1, 0] = r;
                        winningPosition[nTokens - 1, 1] = c;
                    }
                    else
                        nTokens = 0;
                    //if ttw tokens are found: the player has won, return true
                    if (nTokens == _ttw)
                        return true;
                }
            }

            //search diagonal: /
            int nDiags = _rows + _cols - 1;
            for (int d = _ttw - 1; d < nDiags - _ttw + 1; d++)
            {
                nTokens = 0;
                for (int j = 0; j <= d; j++)
                {
                    int r = j;
                    int c = d - r;

                    if (r >= 0 && r < _rows && c >= 0 && c < _cols)
                    {
                        //if token is found
                        if (grid[r, c] == color)
                        {
                            nTokens++;
                            winningPosition[nTokens - 1, 0] = r;
                            winningPosition[nTokens - 1, 1] = c;
                        }
                        else
                            nTokens = 0;
                        //if ttw tokens are found: the player has won, return true
                        if (nTokens == _ttw)
                            return true;
                    }
                }
            }


            //search diagonal: \
            for (int d = _ttw; d < nDiags - _ttw + 2; d++)
            {
                nTokens = 0;
                for (int j = 0; j <= d; j++)
                {
                    int r = j;
                    int c = _cols - (d - r);

                    if (r >= 0 && r < _rows && c >= 0 && c < _cols)
                    {
                        //if token is found
                        if (grid[r, c] == color)
                        {
                            nTokens++;
                            winningPosition[nTokens - 1, 0] = r;
                            winningPosition[nTokens - 1, 1] = c;
                        }
                        else
                            nTokens = 0;
                        //if ttw tokens are found: the player has won, return true
                        if (nTokens == _ttw)
                            return true;
                    }
                }
            }



            //return false if nothing is found
            return false;
        }

        /// <summary>
        /// Finds the uppermost token in column <paramref name="c"/>. 
        /// </summary>
        /// <param name="c">The column to be searched for a token</param>
        /// <returns>The row number r </returns>
        public int findFirstFullRow(int c)
        {
            for (int i = 0; i < _rows; i++)
            {
                if (!isFieldFree(i, c))
                {
                    return i;
                }
            }
            return _rows - 1;
        }

        /// <summary>
        /// Redos the last move done in column c
        /// </summary>
        /// <param name="c">The column where to redo the last move</param>
        public void redoMove(int c)
        {
            int r = findLegalRowInColumn(c);

            //check whether the column is not full
            if (r != -1)
            {
                grid[r + 1, c] = GameColor.Empty;
            }
            else
            {
                // Column full, we remove the top coin.
                grid[0, c] = GameColor.Empty;
            }
        }


    }

    /***********************************************************************************/

    public class MiniMax
    {

        // The colors of MIN and MAX
        private GameColor MAX;
        private GameColor MIN;

        // This board stores the various game situtations which appear while traversing the miniMax tree.
        public RedoBoard miniMaxBoard;

        public MiniMax(GameColor max, GameColor min)
        {
            this.MAX = max;
            this.MIN = min;
        }

        /// <summary>
        /// Starts the MiniMax algorithm
        /// </summary>
        /// <param name="board">The current game state from which to start the search</param>
        /// <param name="depth">The desired depth</param>
        /// <returns>The column where to put the next coin</returns>
        public int minimax(RedoBoard board, int depth)
        {
            miniMaxBoard = board.Clone();

            Node root = new Node(-1, MAX, MIN);

            // Alpha-Beta pruning variables, initialized with highes/smalles values
            int alpha = int.MinValue;
            int beta = int.MaxValue;
            // The highest score
            int score = int.MinValue;
            // The column where we put our next coin.
            int column = 0;

            foreach (Node child in root.getChildren(miniMaxBoard))
            {
                int tmp = this.min(child, depth, alpha, beta);
                // Check if we found a draw, which has a higher rating
                if (score <= tmp && miniMaxBoard.isLegalColumn(child.column))
                {
                    score = tmp;
                    // Remember which draw to make
                    column = child.column;
                }
            }

            return column;
        }

        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MAXs turn.
        /// </summary>
        /// <param name="node">The current node (Max node)</param>
        /// <param name="depth">The current depth, if it equals 1 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The maximum reachable score from node</returns>
        public int max(Node node, int depth, int alpha, int beta)
        {
            try
            {
                // Update game state
                miniMaxBoard.moveTo(MAX, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    return node.getScore(miniMaxBoard);
                }

                // Stores the score of the children
                int score = 0;

                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MAX is maximizing
                    score = Math.Max(alpha, this.min(child, depth - 1, alpha, beta));
                    // Check if we can prun the subtree. We can prun it, if MIN would never 
                    // choose the current state, because he found a better one.
                    if (beta < score)
                    {
                        // MIN never will enter this subtree, we can stop.
                        break;
                    }
                    // Update alpha value
                    alpha = score;
                }

                return alpha;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);

            }
        }

        /// <summary>
        /// Invoked by the MiniMax Algorithm if its MINs turn.
        /// </summary>
        /// <param name="node">The current node (MIN node)</param>
        /// <param name="depth">The current depth, if it equals 1 a leafe is reached</param>
        /// <param name="alpha">The current alpha value</param>
        /// <param name="beta">The current beta value</param>
        /// <returns>The minimum reachable score from node</returns>
        public int min(Node node, int depth, int alpha, int beta)
        {

            try
            {
                // Update game state
                miniMaxBoard.moveTo(MIN, node.column);

                // Check if we reached the desired depth
                if (depth == 0 || node.isTerminal(miniMaxBoard))
                {
                    // We are at the leafs of the tree. Calculate the score of the game state
                    // and give it to the parent node
                    return node.getScore(miniMaxBoard);
                }

                // Stores the score of the children
                int score = 0;

                // Its MINs turn
                foreach (Node child in node.getChildren(miniMaxBoard))
                {
                    // MIN is minimizing (bad states for MAX are good ones for MIN)
                    score = Math.Min(beta, this.max(child, depth - 1, alpha, beta));
                    // Like above we check whether we can prun the subtree
                    if (score < alpha)
                    {
                        break;
                    }
                    // Update beta value
                    beta = score;
                }

                return beta;
            }
            finally
            {
                // Restore the state before this node was visited
                miniMaxBoard.redoMove(node.column);
            }
        }
    }


    /**************************************************************************************/
    public class Node
    {

        // The column the node put its coin
        public int column { get; set; }

        private GameColor MAX;
        private GameColor MIN;

        //sbr: Gewichtung für die Anzahl der Tokens in einer Reihe
        private int[] MAX_ROW = { 1, 2, 10, 1000, 1000, 1000, 1000 };
        private int[] MIN_ROW = { 1, 2, 10, 10000, 10000, 10000, 10000 };

        //sbr: erweitert mit MAX und MIN, da hier für die Score-Berechnung gewusst werden muss, wer ich bin (damit ich bspw. meine Steine zählen kann)
        public Node(int column, GameColor MAX, GameColor MIN)
        {
            this.column = column;
            this.MAX = MAX;
            this.MIN = MIN;
        }

        /// <summary>
        /// Returns the children (game states reachable from the current one) of the node
        /// </summary>
        /// <returns>The child nodes</returns>
        public List<Node> getChildren(RedoBoard state)
        {
            List<Node> children = new List<Node>(7);
            // Create the other game states, which are reachable from this node.
            // There are up to six other states, because there are 7 columns 
            for (int i = 0; i < 7; i++)
            {
                // Check if we can put a coin at column i
                if (state.isLegalColumn(i))
                {
                    children.Add(new Node(i, MAX, MIN));
                }
            }
            return children;
        }

        /// <summary>
        /// Indicates whether the node represents a terminal game state. That is a user finished the game.
        /// </summary>
        /// <param name="board">The game state</param>
        /// <returns></returns>
        public bool isTerminal(RedoBoard state)
        {
            return (state.hasWon(GameColor.Blue) || state.hasWon(GameColor.Red));
        }

        /// <summary>
        /// Returns the calculated score of the current node. The higher the score, the better the state out of the perspective of MAX.
        /// </summary>
        /// <param name="board">The game state</param>
        /// <returns></returns>
        public int getScore(RedoBoard state)
        {
            int myInARow = countMyTokensInARow(state, this.column);
            int opsInARow = countOpsTokensInARow(state, this.column);

            int totalScore = myInARow * MAX_ROW[myInARow - 1] + opsInARow * MIN_ROW[opsInARow - 1];

            Console.WriteLine(this.column + ": " + totalScore);
            return totalScore;
        }

        private int countMyTokensInARow(RedoBoard board, int c)
        {
            return myTokensInARow(board, c);
        }

        private int countOpsTokensInARow(RedoBoard board, int c)
        {
            return opsTokensInARow(board, c);
        }



        /// <summary>
        /// sbr:
        /// Computes the number of token in a row (horizontally, vertically and diagonally) when moving own stone here
        /// </summary>
        /// <param name="c">The column</param>
        /// <param name="board">The board</param>
        /// <returns>The number of tokens I have in a row if moving to column c</returns>
        private int myTokensInARow(RedoBoard board, int c)
        {
            //find accoring row number
            int r = board.findFirstFullRow(c);
            Console.Write(r + " ");

            //if c is illegal column:
            if (r == -1)
                return -1;

            //count stores the maximum number of consecutive tokens in this column
            int count = 0;
            int a = 0;
            int b = 0;

            //search vertical: |
            int countVert = 0;
            a = r - 1;
            b = c;
            while (isMyToken(a, b, board))
            {
                countVert++;
                a--;
            }
            a = r + 1;
            b = c;
            while (isMyToken(a, b, board))
            {
                countVert++;
                a++;
            }
            if (countVert > count)
                count = countVert;

            //search horizontal: -
            int countHor = 0;
            a = r;
            b = c - 1;
            while (isMyToken(a, b, board))
            {
                countHor++;
                b--;
            }
            a = r;
            b = c + 1;
            while (isMyToken(a, b, board))
            {
                countHor++;
                b++;
            }
            if (countHor > count)
                count = countHor;

            //search diagonal1: /
            int countDiag1 = 0;
            a = r + 1;
            b = c - 1;
            while (isMyToken(a, b, board))
            {
                countDiag1++;
                a++;
                b--;
            }
            a = r - 1;
            b = c + 1;
            while (isMyToken(a, b, board))
            {
                countDiag1++;
                a--;
                b++;
            }
            if (countDiag1 > count)
                count = countDiag1;

            //search diagonal2: \
            int countDiag2 = 0;
            a = r + 1;
            b = c + 1;
            while (isMyToken(a, b, board))
            {
                countDiag2++;
                a++;
                b++;
            }
            a = r - 1;
            b = c - 1;
            while (isMyToken(a, b, board))
            {
                countDiag2++;
                a--;
                b--;
            }
            if (countDiag2 > count)
                count = countDiag2;

            return count + 1;
        }

        /// <summary>
        /// sbr:
        /// Computes the number of token in a row (horizontally, vertically and diagonally) when moving a stone here
        /// </summary>
        /// <param name="c">The column</param>
        /// <param name="board">The board</param>
        /// <returns>The number of tokens the opponent has in a row if moving to column c</returns>
        private int opsTokensInARow(RedoBoard board, int c)
        {
            //find accoring row number
            int r = board.findFirstFullRow(c);

            //if c is illegal column:
            if (r == -1)
                return -1;

            //count stores the maximum number of consecutive tokens in this column
            int count = 0;
            int a = 0;
            int b = 0;

            //search vertical: |
            int countVert = 0;
            a = r - 1;
            b = c;
            while (isOpsToken(a, b, board))
            {
                countVert++;
                a--;
            }
            a = r + 1;
            b = c;
            while (isOpsToken(a, b, board))
            {
                countVert++;
                a++;
            }
            if (countVert > count)
                count = countVert;

            //search horizontal: -
            int countHor = 0;
            a = r;
            b = c - 1;
            while (isOpsToken(a, b, board))
            {
                countHor++;
                b--;
            }
            a = r;
            b = c + 1;
            while (isOpsToken(a, b, board))
            {
                countHor++;
                b++;
            }
            if (countHor > count)
                count = countHor;

            //search diagonal1: /
            int countDiag1 = 0;
            a = r + 1;
            b = c - 1;
            while (isOpsToken(a, b, board))
            {
                countDiag1++;
                a++;
                b--;
            }
            a = r - 1;
            b = c + 1;
            while (isOpsToken(a, b, board))
            {
                countDiag1++;
                a--;
                b++;
            }
            if (countDiag1 > count)
                count = countDiag1;

            //search diagonal2: \
            int countDiag2 = 0;
            a = r + 1;
            b = c + 1;
            while (isOpsToken(a, b, board))
            {
                countDiag2++;
                a++;
                b++;
            }
            a = r - 1;
            b = c - 1;
            while (isOpsToken(a, b, board))
            {
                countDiag2++;
                a--;
                b--;
            }
            if (countDiag2 > count)
                count = countDiag2;

            return count + 1;
        }

        /// <summary>
        /// Checks whether my token is on (r,c). 
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <param name="board">The board</param>
        /// <returns>True, if my token is on (r,c). False, if (r,c) is outside the grid. </returns>
        private bool isMyToken(int r, int c, RedoBoard board)
        {
            if (r >= 0 && r < board.Rows && c >= 0 && c < board.Cols)
            {
                if (board.playerAt(r, c) == MAX)
                    return true;
            }
            return false;
        }

        /// <summary>
        /// Checks whether ops token is on (r,c). 
        /// </summary>
        /// <param name="r">The row</param>
        /// <param name="c">The column</param>
        /// <param name="board">The board</param>
        /// <returns>True, if my token is on (r,c). False, if (r,c) is outside the grid. </returns>
        private bool isOpsToken(int r, int c, RedoBoard board)
        {
            if (r >= 0 && r < board.Rows && c >= 0 && c < board.Cols)
            {
                if (board.playerAt(r, c) == MIN)
                    return true;
            }
            return false;
        }
    }



    /******************************************************************************/

    class EngineGroup472 : Engine
    {
        //The opponent
        private GameColor op;

        // This board stores the current game situation
        private RedoBoard board = new RedoBoard(4);

        // Implements the MiniMax algorithm
        private MiniMax miniMax;

        //sbr: Diese Variable zählt die Anzahl der bereits gespielten Züge
        private int anzahlGespielteZuege;

        public EngineGroup472(GameColor me)
        {
            //learn own and opponent's color
            this._me = me;
            switch (me)
            {
                case GameColor.Red:
                    op = GameColor.Blue;
                    break;
                case GameColor.Blue:
                    op = GameColor.Red;
                    break;
                case GameColor.Empty:
                    throw new Exception("Wrong initialization color.");
                default:
                    throw new Exception("Wrong initialization color.");
            }
            miniMax = new MiniMax(me, op);
            anzahlGespielteZuege = 0;
        }

        /// <summary>
        /// Makes a move in the current situation
        /// </summary>
        /// <returns>The row number where to set a token</returns>
        public override int makeMove()
        {

            Console.WriteLine(board);

            int col = 0;
            //sbr: Sollten wir anfangen, setzen wir den ersten Stein immer in die Mitte
            if (board.isBoardFree())
            {
                col = 3;
                anzahlGespielteZuege++;
                board.moveTo(_me, col);
                return col;
            }

            //sbr: Sollten wir nicht anfangen, setzen wir unseren ersten Stein direkt neben den des Gegners
            if (anzahlGespielteZuege == 1)
            {
                int gegnerCol = 0;
                if (_me == GameColor.Blue)
                {
                    for (int i = 0; i < board.Cols; i++)
                    {
                        if (board.playerAt(5, i) == op)
                        {
                            gegnerCol = i;
                            break;
                        }
                    }
                }
                if (gegnerCol < 4)
                {
                    board.moveTo(_me, gegnerCol - 1);
                    anzahlGespielteZuege++;
                    return gegnerCol + 1;
                }
                else
                {
                    board.moveTo(_me, gegnerCol + 1);
                    anzahlGespielteZuege++;
                    return gegnerCol - 1;
                }
            }
            col = miniMax.minimax(board, 0);
            board.moveTo(_me, col);
            anzahlGespielteZuege++;
            return col;
        }

        /// <summary>
        /// Gets the move of the opponent
        /// </summary>
        /// <param name="c">The column where the opponent has moved</param>
        public override void update(int c)
        {
            board.moveTo(op, c);
            Console.WriteLine(board);
            anzahlGespielteZuege++;
        }

        /// <summary>
        /// Called after each engine's turn. null means "nothing to say"
        /// </summary>
        /// <returns>A message a engine can send after each own turn</returns>
        public override string say()
        {
            return "Tobias hat gesetzt. Stefan und Maik bejubeln ihn.";
        }
    }
}
